package a14_Sort;

/**
 * @Author quan
 * @Description 归并排序
 * @Date 2023/4/27 11:30
 */
public class mergeSort {
    public static void main(String[] args) {
        int[] arr = {1,56,23,4,12,9,6,8,17};
        mergeSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
    public static void mergeSort(int[] arr){
        mergeSortInternal(arr,0,arr.length-1);
    }

    /**
     * 在arr[l,r)上进行归并排序
     * @param arr
     * @param l
     * @param r
     */
    private static void mergeSortInternal(int[] arr, int l, int r) {
        //当前数组元素为0或者只有一个
//        if(l >= r){
//            return;
//        }
        //优化2：小数组(64元素以内)直接使用插入排序
        if(r-l <= 64){
            insertSort(arr,l,r);
            return;
        }

        //防止索引越界mid = l+r/2
        int mid = l + ((r-l) >>1);
        //先将原数组一分为二，在子数组上进行归并排序
        mergeSortInternal(arr,l,mid);
        mergeSortInternal(arr,mid+1,r);
        //此时两个子数组已经有序，将这两个子数组合并为一个大的有序数组
        //优化1
        if(arr[mid] > arr[mid+1]){
            merge(arr,l,mid,r);
        }
    }
    private static void insertSort(int[] arr,int l, int r){
        for (int i = l; i <= r; i++) {
            for (int j = i; j > l ; j--) {
                if(arr[j] < arr[j-1]){
                    swap(arr,j,j-1);
                }
            }
        }
    }
    /**
     * 将两个子数组合并为原数组
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        //创建一个大小为r-l+1的数组，该数组与原数组的长度一致，是临时数组
        int[] aux = new int[r-l+1];
        //将原数组的内容都拷贝过来：原数组名称，原数组的开始位置，目标数组的名称，目标数组的开始索引，需要拷贝的长度
        System.arraycopy(arr,l,aux,0,r-l+1);
        //两个子数组的开始位置
        int i = l, j = mid +1;
        //k表示当前原数组合并到哪个位置了
        for (int k = l; k <= r; k++) {
            //子数组1全部拷贝完毕，将子数组2的剩余内容写回arr
            if(i > mid){
                //创建的新数组下标从0开始，但是原数组的索引从l开始，差l的偏移量
                arr[k] = aux[j-l];
                j++;
            } else if (j > r) {
                arr[k] = aux[i-l];
                i++;
            } else if (aux[i-l] <= aux[j-l]) { //两个子数组都没走完,i小
                //稳定性
                arr[k] =  aux[i-l];
                i++;
            } else{
                arr[k] =  aux[j-l];
                j++;
            }
        }
    }
    //交换函数
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
